#!/usr/bin/env python

import sys
import socket
import time
import re
import random
import os
from threading import Thread, Timer, Event, Lock
from optparse  import OptionParser

NONFIFO = 1
SHOW_QUEUE = 1

LOTH = 1 
HITH = 5
FW_TIMEOUT = 3 
ACK_TIMEOUT = 20 
#ACPTNUM = 2
NONFIFO_DELAY = 5
PING_TIMEOUT = 3
SLOW_DOWN = PING_TIMEOUT+1

def string2vector(s):
	return map(int, re.split(' ',s))
def vector2string(v):
	s = str(v[0])
	for x in v[1:]:
		s += ' '+str(x)
	return s	

class msg_server(Thread):
	
	def __init__(self, handler, port=3721):
		Thread.__init__(self)
		sock = socket.socket(
				socket.AF_INET, socket.SOCK_DGRAM)
		self.sock = sock
		sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
		self.port = port
		self.handler = handler

		try:
			sock.bind(('',port))
		except:
			sys.stderr.write("Can't bind to %d\n" % port)
			sys.exit(-1)
		sys.stdout.write("msg server listening on port %d\n"% port)
	

	def run(self):
		while 1:
			try:
				data, addr = self.sock.recvfrom(1024)
#				print 'Got data from %s:%s:%s' %  (addr[0],addr[1], data)
				self.handler.process_msg(data)
			except socket.error, e:
				print "Recv Error"	
class msg_client:
	def __init__(self):
		sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
		self.sock = sock
		self.queue  = []
#		self.qlock = Lock()
		self.nonfifo = NONFIFO
		if self.nonfifo:
			self.start_timer()

	def start_timer(self):
		self.timer = Timer(NONFIFO_DELAY/(len(self.queue)+2), self.timeout)
		self.timer.start()

	def timeout(self):
		if len(self.queue)==0:
			self.start_timer()
			return
		e = self.queue.pop(0)
		self.real_send(e[0],e[1])	
		self.start_timer()

	def send(self, msg, addr):
		if SHOW_QUEUE:
			if random.randint(1,20)<4:
				print "MSG Sending Queue Status", self.queue

		if not self.nonfifo:
			self.real_send(msg,addr)
			return
		# randomize the sending, creating a non-FIFO scenario
		if self.queue==[]:
			rand_delay = 0
		else:	
			rand_delay = random.randint(0, len(self.queue))
		self.queue.insert(rand_delay, (msg, addr))
#		print "NONFIFO QUEUE:",self.queue

#		if rand_delay == 0:
#                        self.real_send(msg, addr)
#                        return
#		ct = time.time()
		'''
		self.qlock.acquire()
		
		if self.queue == []:
			self.queue.append((msg,addr,ct,rand_delay))
			ring = rand_delay
			self.timer = Timer(ring, self.timerout)
			self.timer.start()
			self.ct = time.time()
		else:
			elapsed_time = ct-self.ct
#			print "elapse: ", elapsed_time
			if elapsed_time+rand_delay<self.queue[-1][3]:
				self.queue.append((msg, addr, ct, rand_delay))

#				self.queue[-2][3] -= elapsed_time+rand_delay
				e = self.queue.pop(-2)
				self.queue.insert(-1, (e[0],e[1],e[2],e[3]-(elapsed_time+rand_delay)))

				self.timer.cancel()
				ring = rand_delay
				self.timer = Timer(ring, self.timerout)
				self.timer.start()
				self.ct = time.time()
			elif len(self.queue)==1:
				self.queue.insert(-1, (msg, addr, ct, elapsed_time + rand_delay - self.queue[-1][3]))
			else:
				j = -1
				t_pre = self.queue[j][3]
				t = self.queue[j][3]+self.queue[j-1][3]
				while elapsed_time + rand_delay > t and j-1>0-len(self.queue):
					j -= 1
					t_pre = t
					t += self.queue[j-1][3]
				if j-1 == 0-len(self.queue) and elapsed_time + rand_delay < t:
					j = 0-len(self.queue)

				self.queue.insert(j, (msg, addr, ct, elapsed_time + rand_delay - t_pre))
#				self.queue[j-2][3] = t - elapsed_time + rand_delay
				if j!=0-len(self.queue)+1:
					e = self.queue.pop(j-2)
					self.queue.insert(j-1, (e[0],e[1],e[2],t-(elapsed_time+rand_delay)))
		self.qlock.release()			
		'''


	def real_send(self, msg, addr):
#	def send(self, msg, addr):
		if msg!='':
			try:
				self.sock.sendto(msg, addr)
			except socket.error, e:
				sys.stderr.write("sending error\n")
		else:
			print "empty message!"
			

class file_server:
	def __init__(self, nodes, id, file, autodie):
		self.id = id
		self.autodie = autodie
		self.clients = nodes[0]
		self.servers = nodes[1]
		self.msg_srv = msg_server(handler = self, port = self.servers[self.id][1])
		self.msg_clt = msg_client()
		self.msg_srv.start()
		self.processed = [0]*len(self.clients) #the newest event time for each proc that has been issued
		self.commited = [0]*len(self.clients) # the newest event time for each proc that has been commited
		self.forwarded = []
		self.forwarding = 0
		self.prepare = {}
		self.queue = []
		self.file = file
		f = open(self.file, 'w')
		f.close()
#		self.state = 'IDLE'
		self.leader = 0
		self.ballot = 0
		self.seq = 0
		self.commited_seq = 0
#		self.accepted_ballot = 0
		self.accepted={}
		self.waiting4commit = {}
		self.voting = 0
		self.your_commited_seq = 0

#		self.commited_items_length = 10 
#		self.commited_items={}
	
	def process_msg(self, msg):
		if re.match('^(.+):(.+)$',msg):
			q = re.match('^(.+):(.+)$',msg)
			cmd = q.group(1)
			content = q.group(2)

		if cmd == "REQ":
			#self.seq += 1
			vector = re.split(',',content)
			id = int(vector[0])
#			ballot = int(vector[1])
			print "REQUEST from client %s:" % (vector[0]),
			vector = map(int,vector[1:])
			print vector
			if vector[id]<=self.commited[id]: #finished
				print "\tDuplicated request"
				self.on_operate_finish(id,vector)
			elif vector[id] <= self.processed[id]: #under voting
                                print '\tUnder voting'
				return
			if self.leader!=self.id:
				if not self.forwarded.__contains__(msg):
					self.forwarded.append(msg)
					self.queue_request(msg)
					self.forward2leader()
				else:
					print "Receive a duplicated message which is under processing"	
				return
			self.on_request(id, self.ballot,vector)

		elif cmd == "PREP":
			vector = re.split(',',content)
			id = int(vector[0])
			ballot = int(vector[1])
			print '\n'
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print "PREPARE from server %d with ballot %d" %(id, ballot)
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print '\n'
#			seq = int(vector[2])
			if self.ballot <= ballot:
                                if self.ballot < ballot:
                                        self.leader = id # a potential leader
				print "Greater than mine %d" %self.ballot
				self.ballot = ballot
				self.ack_prepare(id, ballot)
		elif cmd == "ACK":
			vector = re.split(',',content)
			ballot = int(vector[0])
			l = int(vector[1])
			your_commited_seq = int(vector[2])
			print '\n'
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print "Received ACK with %d pending requests" % l 
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print '\n'
			self.on_ack(ballot, l, your_commited_seq, map(int,vector[3:]))# could it be electing for multiple times? ballot different?	
                elif cmd == "PING":
                        vector = re.split(',',content)
			id = int(vector[0])
			vc = vector[1:]
                        self.on_ping(id, vc)
                        
		elif cmd == "ACPT":
			vector = re.split(',',content)
			acceptor_id = int(vector[0])
			id = int(vector[1])
			ballot = int(vector[2])
			seq = int(vector[3])
			vector = map(int, vector[4:])

			if acceptor_id == self.leader and self.forwarding and self.queue[0][0]==id and self.is_same(self.queue[0][1], vector):
					self.forwarding = 0
					self.forward_timer.cancel()
					self.forwarded.pop(0)
					self.queue.pop(0)
					print time.time(), "Succesfully forwarded to leader"
					self.forward2leader()

			if self.id==self.leader and self.voting:
				self.deal_with_pending_msg(id, seq, ballot, vector)
				self.on_vote()

			self.accept(id, ballot,seq,vector)
				#should i change the ballot number?

#		elif cmd == "WRT":
#			q = re.split(',', content)
#			self.on_operate (int(q[0]),q[1])
#			print "OPERATION from link %s" % q[0]
			
#		elif cmd == "RLS":
#			id = int(content)
#			print "RELEASE from link %d" % id
#			self.on_release(id)
		else:
			print "Message Error"

        
	def forward2leader(self):
		if (not self.forwarding) and (not self.voting) and self.forwarded != []:
			msg = self.forwarded[0]
			print time.time(), "Forwarding Request: ", msg, ' to server ', self.leader
			self.msg_clt.send(msg, self.servers[self.leader])
			self.forward_timer = Timer(FW_TIMEOUT, self.handle_forward_timeout)
			self.forward_timer.start()
			self.forwarding = 1
		#start timer here

	def handle_forward_timeout(self):
		print time.time(), "Leader "+str(self.leader)+" Timeout!"
		self.forwarding = 0
		#try to be leader or vote another one
		self.leader = self.leader+1
		if self.leader<self.id:
			print "Forward to the server "+str(self.leader)
			self.forward2leader()
		else:	
			self.leader -= 1
			self.self_elect()

	def self_elect(self):
		self.voting = 1
		self.forwarded = []  # note: discard all the requests (already in queue), if I can't reach the leader, and I am trying to be the leader
		self.ballot+=1
		print "Increase ballot to", self.ballot
		print "Pending Requests,",self.accepted.keys()
		for prop in self.accepted.keys():
#		if prop[2]>self.commited_seq and prop[2]<=self.seq:
			y={}
			y['id']=prop[0]
			y['b']=prop[1]
			y['v']=string2vector(prop[3])
#			y['votes']=1
#			y['voted']=False
			self.prepare[prop[2]]=y
#		for seq in range(self.commited_seq+1, self.seq+1):
#			if not self.prepare.has_key(seq):
#				y={}
#				y['id']=prop[0]
#				y['b']=0
#				y['v']=None
#				y['votes']=1
#				y['voted']=False
#				self.prepare[seq]=y
		msg = "PREP:%d,%d" % (self.id, self.ballot)
		print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
		print "Prepare ballot %d" %self.ballot
		print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
		for i in range(len(self.servers)):
			if i != self.id:
				self.msg_clt.send(msg, self.servers[i])
		#should have timeout here
	def ack_prepare(self, id, ballot):  #now we can remove the commited queue # think about how to clear prepare after
		msg = "ACK:%d,%d,%d" % (ballot,len(self.accepted), self.commited_seq)
		print "ACK with my pending requests:"
		for prop in self.accepted.keys():
			id = prop[0]
			b = prop[1]
			v = string2vector(prop[3])
			seq = prop[2]
			print '\tseq #',seq,'id',id,'ballot',b,'value',v
			msg+=',%d,%d,%d'%(id,seq,b)
			for i in v:
				msg+=',%d'%i
		if len(self.accepted)==0:
			print "\tEmpty"
		self.accepted={} #note : clear the queue?
		self.msg_clt.send(msg, self.servers[id])
	
#	def ack_prepare(self, id, ballot, seq):
#		if seq <= self.commited_seq-len(self.commited_items)+1:
#			print "Tooooooold! Have been commited years ago!"
#			b = self.ballot
#			v = 'True'
#		elif seq <= self.commited_seq:
#			b = self.commited_items[seq][0]
#			v = self.commited_items[seq][1]
#		else:
#			found = False
#			for req in self.accepted.keys():
#				if req[2]==seq:
#					b = req[1]
#					v = string2vector(req[3])
#					found=True
#					break				
#			if not found:
#				b = 0
#				v = 'None'
#
#		msg = "ACK:%d,%d,%d" %(seq,ballot,b)
#		if v=="True" or v=="None":
#			msg += ','+v
#		else:
#			for i in v:
#				msg+=',%d'%i
#		self.msg_clt.send(msg, self.servers[id])		

        def on_ping(self, id, vector):
                msg = 'ECHO:'
                for i in vector:
                        msg +=i+','
                msg = msg[:-1]
                print msg
                self.msg_clt.real_send(msg, self.clients[id])
                print msg, ' to client ', id

	def on_ack(self, ballot, l, your_commited_seq, vector):
		if self.voting == 0:
                        return

		vl = len(self.clients)+3

		if self.your_commited_seq > your_commited_seq:
                        self.your_commited_seq = your_commited_seq

		self.voting+=1
		for i in range(l):
			self.deal_with_pending_msg(vector[i*vl],vector[i*vl+1],vector[i*vl+2],vector[(i*vl+3):(i+1)*vl])
		self.on_vote()	

	def on_vote(self):
                if self.prepare.keys()==[]:
                        max_seq = self.your_commited_seq
		else:
                        max_seq = max(self.prepare.keys())
                if self.voting > float(len(self.servers))/2 and len(self.prepare)==max_seq-self.your_commited_seq:
			print '\n'
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print "Collected %d votes, become the LEADER" % self.voting 
			print "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
			print '\n'
			self.leader = self.id
			self.voting = 0
			for seq in sorted(self.prepare.keys()):
				y = self.prepare[seq]
				self.accept(y['id'], self.ballot, seq, y['v'])
				if self.queue.__contains__((y['id'],y['v'])): # clear duplicated request
					self.queue.remove((y['id'],y['v']))
			self.prepare = {}
			self.on_release() #start to find the next one in the queue


	def deal_with_pending_msg(self, id, seq, ballot, vector):
		if self.prepare.has_key(seq):
			y = self.prepare[seq]
			if y['b']< ballot:
				y['v']=vector
				y['b']=ballot
				y['id']=id
		else:
			self.prepare[seq]={}
			y = self.prepare[seq]
			y['v']=vector
			y['b']=ballot
			y['id']=id


	def queue_request(self, msg):			
		q = re.match('^(.+):(.+)$',msg)
		cmd = q.group(1)
		content = q.group(2)
		
		vector = re.split(',',content)
		id = int(vector[0])
		ballot = int(vector[1])
		print "REQUEST from client %s" % (vector[0]),
		vector = map(int,vector[1:])
		print vector
		if vector[id]<=self.commited[id]: #finished
			self.on_operate_finish(id,vector)
		elif vector[id] < self.processed[id]: #under voting
			return
		self.queue.append((id,vector))
		print "Add to my local queue"
		print "Request Queue Status:", self.queue
			
#	def cache_commited(self,ballot,seq,vector):
#		if len(self.commited_items)==self.commited_items_length:
#			self.commited_items.pop(seq-self.commited_items_length)
#		self.commited_items[seq]=(ballot,vector)	

	def commit(self, id, ballot, vector, seq):
		time_vector = 'client %d ballot %d sequence number %d:' % (id, ballot, seq)
		for i in vector:
			time_vector += "%d " % i
		f=open(self.file, 'a')
		f.write(time_vector+'\n')
		f.close()
		self.commited[id] = vector[id]
		self.on_operate_finish(id, vector)

	def on_operate_finish(self, id, vector):
		msg = 'ACK:%d' % self.leader 
		for i in vector:
			msg += ',%d' % i
		if self.leader == self.id:
			self.msg_clt.send(msg, self.clients[id])

	def on_request(self, id, ballot, vector):
		#note: requests shoule change to parallel
#		if self.state == 'IDLE':
		if self.queue.__contains__((id, vector)): #if has, do not append
                        return
		if self.is_next(id, vector):
			self.seq += 1
			self.processed[id] += 1
			self.accept(id, ballot, self.seq, vector)
#			print "accepted", self.processed
		else:
                        self.queue.append((id, vector))
#		else:
#			self.queue.append((id, vector))

	def is_same(self, a, b):
		for i in range(len(a)):
			if a[i]!=b[i]:
				return False
		return True	

	def is_next(self, id, vector):
		waiting = self.processed[:]
		waiting[id] += 1

		result = True
		if vector[id] != waiting[id]:
			return False
		else:
			for i in range(len(vector)):
				if i == id:
					continue
				if vector[i]>waiting[i]:
					result=False
					break
		return result

	def accept(self, id, ballot, seq, vector):
		if ballot < self.ballot:
			return
		if vector[id]<=self.commited[id]: 
			return
		if self.waiting4commit.has_key(seq):
			return
		if self.seq < seq:  #could cause problem?
			self.seq=seq  # or not
		for i in range(len(vector)):	
			if self.processed[i]<vector[i]:
				self.processed[i]=vector[i]
#				print "Accepted",self.processed	

		msg = 'ACPT:%d,%d,%d,%d' % (self.id,id,ballot,seq)
		for j in vector:
			msg += ",%d" % j
		vs=vector2string(vector)
		if self.accepted.has_key((id,ballot,seq,vs)):
			self.accepted[(id,ballot,seq,vs)] += 1
			if self.accepted[(id,ballot,seq,vs)]>float(len(self.servers))/2:
                                print 'Receive ', msg, ' from the majority'
				if seq<=self.commited_seq:            #already commited
					# print "ballot %d, client %d, req %d, vector" % (ballot,id,seq),
					print vector,
					print "Already commited, ignore here"
				else:
					self.waiting4commit[seq]=(id,ballot,vector)
					while self.waiting4commit.has_key(self.commited_seq+1):
						self.commited_seq+=1
						req = self.waiting4commit[self.commited_seq]
						self.commit(req[0],req[1],req[2],self.commited_seq)
#						self.cache_commited(req[1],self.commited_seq,req[2]) #cache some for replying prepare msg from new leaders
						print "\nCMMT ballot %d,client %d, req %d, vector" % (req[1],req[0],self.commited_seq),
						print req[2],'\n'
				self.accepted.pop((id, ballot,seq,vs))
				self.on_release()
		else:
                        print 'Broadcast ', msg, ' to other servers'
			for i in range(len(self.servers)):
                                '''
                                if self.autodie == 'y':
                                        if i == ACPTNUM:
                                                print 'I am dying. Bye~~'
                                                exit()
                                '''
				if i != self.id:
                                        # print 'Send ', msg, ' to sever ',i 
					self.msg_clt.send(msg, self.servers[i])
					
			if self.leader==self.id:		
				self.accepted[(id,ballot,seq,vs)]=1
			else:
				self.accepted[(id,ballot,seq,vs)]=2

#			print "ACPT ballot %d, client %d, req %d, vector" % (ballot, id, seq) ,
#			print vector

#			self.state = 'BUSY'
			if self.accepted[(id,ballot,seq,vs)]>float(len(self.servers))/2:
                                print 'Receive ', msg, ' from the majority'
				self.waiting4commit[seq]=(id,ballot,vector)
				while self.waiting4commit.has_key(self.commited_seq+1):
					self.commited_seq+=1
					req = self.waiting4commit[self.commited_seq]
					self.commit(req[0],req[1],req[2], self.commited_seq)
#					self.cache_commited(req[1],self.commited_seq,req[2]) #cache some for replying prepare msg from new leaders
					print "\nCMMT ballot %d,client %d, req %d, vector" % (req[1],req[0],self.commited_seq ),
					print req[2],'\n'
				self.accepted.pop((id, ballot,seq,vs))
					#	self.granted_time = vector[:]
#			self.accepted_ballot = ballot
			if ballot>self.ballot:
				self.ballot = ballot

	def on_release(self):
		print "Newest accepted:", self.processed
		print "Request Queue Status:", self.queue
#		self.state = 'IDLE'
		for req in self.queue:
			id = req[0]
			vector = req[1]
			#clear the stale requests
			greater = False
			for i in range(len(vector)):
				if vector[i]>self.commited[i]:
					greater = True
					break
			if greater == False:
				self.queue.remove(req)
				continue

			if self.is_next(id, vector):
				self.seq+=1
				self.processed[id] += 1
#				print "Accepted:", self.processed
				self.queue.remove(req)
				self.accept(id,self.ballot,self.seq,vector)


class file_client:
	def __init__(self, nodes, id):
		self.clients = nodes[0]
		self.server = nodes[1]
		self.leader = 0
		self.serverNum = len(self.server)
		self.id = id
		self.msg_srv = msg_server(handler = self, port = self.clients[id][1])
		self.msg_clt = msg_client()
		self.vectorClock = [0]*len(self.clients)
		self.vcLock = Lock()
		self.timeoutflag = 0
		self.pendingTimer = []
		self.pendingMsg = []
		self.pendingLock = Lock()
		
		self.msg_srv.start()

	def process_msg(self, msg):
		if re.match('^(.+):(.+)$',msg):
			q = re.match('^(.+):(.+)$',msg)
			cmd = q.group(1)
			content = q.group(2)
		else:
			print "Message Error"
			return

		if cmd =="EVT":
			vector = re.split(',',content)
			id = int(vector[0])
			print "EVENT from client %s :" % vector[0],
			vector = map(int,vector[1:])
			self.on_event(id, vector)

		elif cmd == "ACK":
                        vector = re.split(',', content)
			self.leader  = int(vector[0])
                        vector = map(int, vector[1:])
			self.on_ack(vector)
		elif cmd == "ECHO":
                        self.ping_timer.cancel()
                        items = content.split(',')
                        vc = map(int, items)
                        i = self.pendingMsg.count(vc)
                        if i < 1:
                                print 'The msg already received ACK. Ignore echo msg.'
                                self.timeoutflag = 0
                                return
                        i = self.pendingMsg.index(vc)
                        if i != 0:
                                print 'The echo msg is not corrsepoinding to the first msg in the pending queue? Ignore.'
                                self.timeoutflag = 0
                                return 
                        
                        self.pendingLock.acquire()
                        vc = self.pendingMsg.pop(0)
                        self.pendingTimer.pop(0)
                        self.pendingLock.release()
                        
                        # resend the msg
                        msg = "REQ:%d" % self.id
                        for i in vc:
                               msg += ",%d" % i 
                        self.msg_clt.send(msg, self.server[self.leader])
                        print 'The leader is still there.'
                        print 'Resend: ', msg,  ' to leader ', self.leader
                        ack_timer = Timer(ACK_TIMEOUT, self.ack_timeout_handler)
                        ack_timer.start()
                        self.pendingLock.acquire()
                        self.pendingTimer.append(ack_timer)
                        self.pendingMsg.append(vc)
                        self.pendingLock.release()
                        
                        self.timeoutflag = 0
			
		else:
			print "Message Error"

			
	def on_ack(self, vector):
                print vector, "Acked"
		self.pendingLock.acquire()
		i = self.pendingMsg.count(vector)
		if i < 1:
                        print 'No pending msg corresponding to the ack msg. Ignore'
                        return
                i = self.pendingMsg.index(vector)
                self.pendingTimer[i].cancel()
		self.pendingTimer.pop(i)
                self.pendingMsg.pop(i)
		self.pendingLock.release()		 
                

	def on_event(self, id, vector):
                self.vcLock.acquire()
		print self.vectorClock, '+',
                for i in range(len(vector)):
                        self.vectorClock[i] = max(self.vectorClock[i], vector[i])
                print vector, '=', self.vectorClock
		self.vcLock.release()
	
	def send_event(self, id):
                nb = self.clients[id]
		msg = "EVT:%d" % self.id
		self.vcLock.acquire()
                for i in self.vectorClock:
                        msg += ",%d" % i
		self.vcLock.release()	
                self.msg_clt.send(msg, nb)

	def send_request(self):
                msg = "REQ:%d" % self.id
                tmpClock = []
                self.vcLock.acquire()
                self.vectorClock[self.id] += 1
                for i in self.vectorClock:
                        msg += ",%d" % i
                        tmpClock.append(i)
		self.vcLock.release()	
#		print self.server
		# set ACK Timer
		self.pendingLock.acquire()
		self.msg_clt.send(msg, self.server[self.leader])
		print 'Send msg ', msg, ' to server ', self.leader
		ack_timer = Timer(ACK_TIMEOUT, self.ack_timeout_handler)
		ack_timer.start()
                self.pendingTimer.append(ack_timer)
                self.pendingMsg.append(tmpClock)
		self.pendingLock.release()

        def ack_timeout_handler(self):
                print 'Penging msg: ', self.pendingMsg
                while self.timeoutflag == 1:
                        print 'Previous msg timed out. Wait...'
                        time.sleep(SLOW_DOWN)  
                self.timeoutflag = 1
        
                msg = 'PING:%d' % self.id
                vc = self.pendingMsg[0]
                print 'Handle ', vc, 'time out'
                for i in range(len(vc)):
                        msg +=','+str(vc[i])
                self.msg_clt.real_send(msg, self.server[self.leader])
                print msg, ' the leader ', self.leader
                self.ping_timer = Timer(PING_TIMEOUT, self.ping_timeout_handler)
		self.ping_timer.start()

	def ping_timeout_handler(self):
                print 'Ping timeout'
                print 'The leader ', self.leader, ' died.'
                self.leader = (self.leader+1)%self.serverNum
                if len(self.pendingMsg) == 0:
                        return
                self.pendingLock.acquire()
                vc = self.pendingMsg.pop(0)
                self.pendingTimer.pop(0)
		self.pendingLock.release()
		
		# resend the msg
                msg = "REQ:%d" % self.id
		for i in vc:
                       msg += ",%d" % i 
                self.msg_clt.send(msg, self.server[self.leader])
                print 'Resend: ', msg,  ' to server ', self.leader
                self.pendingLock.acquire()
		ack_timer = Timer(ACK_TIMEOUT, self.ack_timeout_handler)
		ack_timer.start()
		self.pendingTimer.append(ack_timer)
                self.pendingMsg.append(vc)
                self.pendingLock.release()
                # this timeout msg has been handled
                self.timeoutflag = 0
                '''
                i = 1
                if self.serverNum%2 == 0:
                        maj = self.serverNum/2
                else:
                        maj = self.serverNum/2+1
                while i <= maj:
                        if self.ping_server(tryleader):
                                self.leader = tryleader
                                print '\tI will send msg to server ', self.leader
                                break
                        else:
                                tryleader = (tryleader+1)%self.serverNum
                        i += 1
                if i > maj:
                        print 'The majority of servers died. I will stop'
                        self.evt_timer.cancel()
                        self.req_timer.cancel()
                        exit()
                '''

                '''                                
                if len(self.pendingMsg) == 0:
                        return
                self.pendingLock.acquire()
                vc = self.pendingMsg.pop(0)
                self.pendingTimer.pop(0)
		self.pendingLock.release()
		
		# resend the msg
                msg = "REQ:%d" % self.id
		for i in vc:
                       msg += ",%d" % i 
                self.msg_clt.send(msg, self.server[self.leader])
                print 'Resend: ', msg,  ' to server ', self.leader
		ack_timer = Timer(ACK_TIMEOUT, self.ack_timeout_handler)
		ack_timer.start()
		self.pendingLock.acquire()
                self.pendingTimer.append(ack_timer)
                self.pendingMsg.append(vc)
                self.pendingLock.release()
		'''

	def evt_timeout_handler(self):
		rnd_id = random.randint(0, len(self.clients)-1)
		if rnd_id != self.id:
			self.send_event(rnd_id)
		self.evt_timer = Timer(random.randint(LOTH, HITH), self.evt_timeout_handler)
		self.evt_timer.start()

	def req_timeout_handler(self):
                '''
                while self.timeoutflag == 1:
                        print 'Previous msg timed out. Slow down...'
                        time.sleep(SLOW_DOWN)
                '''
                if len(self.pendingMsg) != 0:
                        self.req_timer = Timer(random.randint(LOTH, HITH), self.req_timeout_handler)
                        self.req_timer.start()
                        return
		self.send_request()
		self.req_timer = Timer(random.randint(LOTH, HITH), self.req_timeout_handler)
		self.req_timer.start()


	def run(self):
		self.evt_timer = Timer(random.randint(LOTH, HITH), self.evt_timeout_handler)
		self.req_timer = Timer(random.randint(LOTH, HITH), self.req_timeout_handler)
		self.evt_timer.start()
		self.req_timer.start()

if __name__=='__main__':
	
	parser = OptionParser()
	
	parser.add_option("-s", "--server", action="store_true", default=False)
	parser.add_option("-c", "--client", action="store_true", default=False)

	parser.add_option("-f", "--file", 
			  dest="filename", default = "fs.log",
	                  help="file name on the server")
	parser.add_option("-d", "--autodie", 
			  dest="autodie", default = "n",
	                  help="file name on the server")
	parser.add_option("-i", "--id",
	                  dest="id", default=0, type = "int",
			  help="process id, 0 for server")
	parser.add_option("", "--server-config", type = "string",
			  dest="server_config_file", default = "paxos_servers.config",
			  help="server config file name")
	parser.add_option("", "--client-config", type = "string",

			  dest="client_config_file", default = "paxos_clients.config",
			  help="client config file name")
	(options, args) = parser.parse_args()

	clients=[]
	f=open(options.client_config_file)
	for l in f.readlines():
		q = re.split('\s+',re.split('\n',l)[0])
		c = (q[1],int(q[2]))
		clients.append(c)
	servers=[]
	f=open(options.server_config_file)
	for l in f.readlines():
		q = re.split('\s+',re.split('\n',l)[0])
		s = (q[1],int(q[2]))
		servers.append(s)

	nodes = (clients, servers)	

	if options.server:
		print "*****Server No.%d*****" % options.id
		proc = file_server(nodes, options.id, str(options.id)+'-'+options.filename, options.autodie)
	else:
		print "*****Client No.%d*****" % options.id
		proc = file_client(nodes, options.id)
		proc.run()
